package Preferred_algorithm.Topic5_Bit_Arithmetic_Algorithms;

public class Topic5_Bit_Arithmetic_Algorithms {
    // blog:
    //https://blog.csdn.net/2402_84916296/article/details/144339142?spm=1001.2014.3001.5501
    // https://blog.csdn.net/2402_84916296/article/details/144338751?spm=1001.2014.3001.5501

    //判定字符是否唯一
    //https://leetcode.cn/problems/is-unique-lcci/description/

    //方法一：使用哈希表
    public boolean isUnique(String astr) {
        int [] hash = new int[26];
        char[] s = astr.toCharArray();

        for(int i = 0 ; i<s.length; i++){
            int index = s[i]-'a';
            hash[index]++;
        }

        for(int i = 0; i<hash.length; i++){
            if(hash[i]>1)return false;
        }
        return true;
    }

    //方法二：使用位运算
    public boolean isUnique1(String astr) {

        int n = astr.length();
        int bitMap = 0;

        for(int i = 0; i<n ; i++){
            int x  = astr.charAt(i)-'a';
            if(((bitMap>>x)&1)==1){
                return false;
            }
            bitMap |= (1<<x);
        }
        return true;
    }


    //268.丢失的数字
    //https://leetcode.cn/problems/missing-number/description/
    public int missingNumber(int[] nums) {
        int ret = 0;
        for(int x : nums){
            ret ^= x ;
        }
        for(int i = 0 ; i < nums.length+1; i++){
            ret ^= i;
        }
        return ret;
    }


    //两数之和
    //https://leetcode.cn/problems/sum-of-two-integers/
    public int getSum(int a, int b) {

        while (b != 0) { // 异或(无进位相加)的结果^缺失的进位，直到缺失进位为0

            int x = a ^ b; // 无进位相加
            int carry = (a & b) << 1; // 求出进位
            a = x;
            b = carry;
        }

        return a;
    }

    //137.只出现一次的数字Ⅱ
    //https://leetcode.cn/problems/single-number-ii/description/
    public int singleNumber2(int[] nums) {
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            int tmp = 0;
            for (int j = 0; j < nums.length; j++) {
                if (((nums[j] >> i) & 1) == 1) {
                    tmp++;
                }
            }
            if (tmp % 3 == 1) {
                ret |= (1 << i);
            }
        }
        return ret;
    }

    //消失的两个数字
    //https://leetcode.cn/problems/missing-two-lcci/description/
    public int[] missingTwo(int[] nums) {
        int tmp = 0;
        for (int x : nums)
            tmp ^= x;
        for (int i = 1; i <= nums.length + 2; i++) {
            tmp ^= i;
        }

        int diff = 0 ;
        while(true){
            if(((tmp>>diff)&1)==1){
                break;
            }
            diff++;
        }

        int [] ret = new int[2];

        for(int x : nums){
            if(((x>>diff)&1)==0)ret[0] ^= x;
            else ret[1] ^= x;
        }

        for(int i = 1; i <= nums.length+2; i++){
            if(((i>>diff)&1)==0)ret[0] ^= i;
            else ret[1] ^= i ;
        }
        return ret;
    }


    //191. 位1的个数
    //https://leetcode.cn/problems/number-of-1-bits/
    public int hammingWeight(int n) {
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            if (((n >> i) & 1) == 1)
                ret++;
        }
        return ret;
    }

    // 338.比特位计数
    //https://leetcode.cn/problems/counting-bits/description/
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < 32; j++) {
                if (((i >> j) & 1) == 1) {
                    ans[i]++;
                }
            }
        }
        return ans;
    }

    //461.汉明距离
    //https://leetcode.cn/problems/hamming-distance/
    public int hammingDistance(int x, int y) {
        int ret = 0;
        int tmp = x^y;
        for(int i = 0 ; i < 32 ; i++){
            if(((tmp>>i)&1)==1){
                ret++;
            }
        }
        return ret;
    }

    //136.只出现一次的数字Ⅰ
    //https://leetcode.cn/problems/single-number/description/
    public int singleNumber1(int[] nums) {
        int ret = 0;
        for(int x : nums)ret^=x;
        return ret;
    }

    //260.只出现一次的数字Ⅲ
    //https://leetcode.cn/problems/single-number-iii/
    public int[] singleNumber(int[] nums) {
        int tmp = 0;
        for(int x : nums){
            tmp ^= x;
        }

        int diff = 0;
        while(true){
            if(((tmp>>diff)&1)==1){
                break;
            }
            diff++;
        }
        int[] ret = new int[2];
        for(int x : nums){
            if(((x>>diff)&1)==0)ret[0] ^= x;
            else ret[1] ^= x;
        }
        return ret;
    }

}
